#include <iostream>
using namespace std;
const int initsize = 20;
//单链表
typedef struct LNode
{
    int data;
    LNode *next;
} LNode, *LinkList;
//双链表
typedef struct DLNode
{
    int data;
    DLNode *next;
    DLNode *prior;
} DLNode, *DLinkList;
void init(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode)); //申请一个头节点
    L->next = NULL;
}
//返回值不知道该返回什么
LNode *headInsert(LinkList &L, int value)
{
    LNode *s;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = value;
    s->next = L->next, L->next = s;
    return s;
}
LNode *getElem(LinkList &L, int pos)
{
    //    从第一个位置开始
    LNode *p = L->next;
    if (pos == 0)
        return L;
    else if (pos < 1)
        return NULL;
    for (int i = 1; i < pos && p; i++)
        p = p->next;
    return p;
}
//第i个节点后插入新节点
bool insert(LinkList &L, int pos, int value)
{
    LNode *temp;
    temp = getElem(L, pos);
    //    如果找不到对应元素位置
    if (!temp)
        return false;
    LNode *s = (LinkList)malloc(sizeof(LNode));
    s->next = temp->next, temp->next = s;
    s->data = value;
    return true;
}
LNode *tailInsert(LinkList &L, int value)
{
    LNode *temp = L;
    while (temp->next != NULL)
        temp = temp->next;
    LNode *s = (LinkList)malloc(sizeof(LNode));
    s->next = NULL, temp->next = s;
    s->data = value;
    return s;
}
void display(LinkList L)
{
    LNode *p = L->next;
    while (p != NULL)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}
// 删除第一个元素
void del_first(LinkList &L)
{
}
// 删除最后一个元素
bool del_tail(LinkList &L)
{
    //    指向头节点 当前节点的上一个节点
    LNode *p = L, *p_prior = L;
    //    空表什么都不用做
    if (p->next == NULL)
        return false;
    p = p->next;
    //    cout<<p->data<<endl;
    //    找到倒数第二个元素
    while (p->next != NULL)
        p_prior = p, p = p->next;
    free(p);
    p_prior->next = NULL;
    //    cout<<p_prior->data<<endl;
    return true;
}
// 随机指定数值的删除  只能删除第一个遇到的value;
bool delet(LinkList &L, int value)
{
    LNode *p = L, *p_prior = L;
    if (p->next == NULL)
        return false;
    p = p->next;
    //  遍历
    while (p->next != NULL)
    {
        //        套用模板 更换if内的条件可实现各种del操作
        if (p->data == value)
            break;
        p_prior = p, p = p->next;
    }
    //    cout<<p->data<<" "<<p_prior->data<<endl;
    p_prior->next = p->next;
    if (p->data == value)
    {
        free(p);
        return true;
    }
    //    没找到value
    else
        return false;
}
//习题1 删除所有x 不带头节点
void del_all_x(LinkList &L, int X)
{
    LNode *p;
    if (L == NULL)
        return;
    p = L;
    if (L->data == X)
    {
        p = L, L = L->next, free(p);
        //        因为以及指向下一个节点了 如果 L.next 会漏
        del_all_x(L, X);
    }
    else
        del_all_x(L->next, X);
}
//习题2 带头节点 删除所有X 非递归
void del_all_x_2(LinkList &L, int x)
{
    LNode *p = L->next, *p_prior = L, *q;
    while (p != NULL)
    {
        if (p->data == x)
            //            更新p_prior p 释放p
            q = p, p = p->next, p_prior->next = p, free(q);
        else
        {
            p_prior = p, p = p->next;
            //            cout<<p->data<<endl;
        }
    }
}
// 习题3 利用递归实现逆向输出链表元素 容易爆栈  时间复杂度O(n)
LNode *r_print(LinkList &L)
{
    if (L == NULL)
        return NULL;

    r_print(L->next);
    if (L != NULL)
        cout << L->data << " ";
}
//习题4 删除链表中最小的数字
LinkList del_min(LinkList &L)
{
    //    暂定第一个是最小的
    LNode *m_pre = L, *m = L->next, *p = L->next, *p_prior = L;
    //    遍历 讲最小的元素保存在m中 最小元素的前驱
    while (p != NULL)
    {
        if (p->data < m->data)
            m = p, m_pre = p_prior;
        p_prior = p, p = p->next;
    }
    m_pre->next = m->next;
    free(m);
    return L;
}
//习题5 反转链表 时间复杂度O(n),空间复杂度O(1);
LinkList reverse(LinkList &L)
{
    LNode *p, *r;
    p = L->next; // 指向第一个元素
                 //    清除原来的头节点 最后一个元素会指向原链表的第一个元素
    L->next = NULL;
    //    使用p遍历原链表 r指向下一个元素 头插法实现倒序p.next=L.next
    while (p != NULL)
        r = p->next, p->next = L->next, L->next = p, p = r;

    return L;
}
//习题6 排序
void sort(LinkList &L)
{
    //    朴素算法 每次从头节点开始遍历然后插入
    LNode *p, *pre, *r;
    p = L->next;                 // 从第一个元素开始
    r = L->next;                 //用来保存原数组的需要从新插入的数字
    r = p->next, p->next = NULL; // 用r 保存原链表新链表的尾指针设置成NULL
    while (r != NULL)
    {
        //        r指向下一个位置 temp
        LNode *temp = r;
        r = r->next;
        pre = L;
        p = L->next;
        //        遍历新链表 将r插入合适的位置
        while (p != NULL && temp->data > p->data)
            pre = p, p = p->next;
        //        插入r
        temp->next = p, pre->next = temp;
    }
}
void sort_2(LinkList &L)
{
    //    先给数字取出来然后 快排 再重新挨个填回去 时间复杂度O(nlogn)
}
//习题8 找公共节点 先别运行 肯有问题
LNode *get_common_elem(LinkList &A, LinkList &B)
{
    //    原理： 出去开头不一样 公共节点到结束应该两个链表完全相同 长节点开头超出的一段一定不是公共节点
    int len_a, len_b;
    LNode *p = A->next;
    while (p != NULL)
        len_a++, p = p->next;
    p = B->next;
    while (p != NULL)
        len_b++, p = p->next;
    if (len_a > len_a)
    {
        p = A->next;
        while (len_a > len_b)
            len_a--, p = p->next;
        LNode *p2 = B->next;
        //        同步向后移动找公共节点
        while (p != NULL && p != p2)
            p = p->next, p2 = p2->next;
        return p;
    }
    else
    {
        p = B->next;
        while (len_b > len_a)
            len_b--, p = p->next;
        LNode *p2 = B->next;
        //        同步向后移动找公共节点
        while (p != NULL && p != p2)
            p = p->next, p2 = p2->next;
        return p;
    }
    //    没有公共节点
    return NULL;
}
//习题9 不适应额外空间 递增次序输出最小值 并释放空间
void delByOrder(LinkList &head)
{
    //    while (head->next!=NULL){
    //        cout<<head->next->data<<" ";
    //        head=head->next;
    //    }
    //    cout<<endl;
    //    题目要求头节点为head
    while (head->next != NULL)
    {
        //        冒泡找最小
        LNode *pre = head, *p = pre->next, *u; // pre 存储每轮最小值的前驱
        while (p->next != NULL)
        {
            if (p->next->data > pre->next->data)
                pre = p;
            p = p->next;
        }
        cout << pre->next->data << " ";
        u = pre->next;
        pre->next = u->next;
        free(u);
    }
    //    释放头节点 容易忘记
    //    free(head);
}
//习题10 拆分奇数链 偶数链
LinkList discreat(LinkList &A)
{
    LinkList B = (LinkList)malloc(sizeof(LNode));
    LNode *p = A->next, *ra = A, *rb = B;
    for (int i = 1; p != NULL; p = p->next, i++)
    {
        if (i % 2)
            ra->next = p, ra = p;
        else
            rb->next = p, rb = p;
    }
    //    最后将两个新链表末尾指针设置为NULL
    ra->next = rb->next = NULL;
    return B;
}
// 习题 11 得到奇数链 反转偶数链(采用头插法）
LinkList discreat_2(LinkList &A)
{
    LinkList B = (LinkList)malloc(sizeof(LNode));
    LNode *p = A->next, *ra = A, *q;
    B->next = NULL;
    int i = 1;
    while (p != NULL)
    {
        //        用for 不方便
        if (i % 2)
        {
            ra->next = p;
            ra = p;
            p = p->next;
        }
        else
            q = p, p = p->next, q->next = B->next, B->next = q;
        i++;
    }
    ra->next = NULL;
    return B;
}
// 习题12 链表去重 只适用于有序表
void del_same(LinkList &L)
{
    LNode *p = L->next, *q;
    if (p == NULL)
        return;
    while (p->next != NULL)
        if (p->data == p->next->data)
        {
            q = p->next, p->next = q->next;
            free(q);
        }
        else
            p = p->next;
}
//习题13 双指针链表合并 并改为降序 只适用于有序双链表
LinkList mergeList(LinkList &A, LinkList &B)
{
    LNode *pa = A->next, *pb = B->next, *r;
    //     为了不影响其他使用B的函数 这里就不free(B)了
    //    free(B);
    A->next = NULL; // 初始 设置为空

    while (pa && pb)
    {
        //        将A，B中较小的数头插进入A
        if (pa->data < pb->data)
            r = pa->next, pa->next = A->next, A->next = pa, pa = r;
        else
            r = pb->next, pb->next = A->next, A->next = pb, pb = r;
    }
    while (pa)
        r = pa->next, pa->next = A->next, A->next = pa, pa = r;
    while (pb)
        r = pb->next, pb->next = A->next, A->next = pb, pb = r;

    return A;
}
//习题 14 求公共共有的元素 产生新的链表
LinkList get_common(LinkList &A, LinkList &B)
{
    LNode *pa = A->next, *pb = B->next, *rc, *s;
    LinkList C = (LinkList)malloc(sizeof(LNode));
    C->next = NULL; //初始设置为空
    rc = C;
    while (pa && pb)
    {
        if (pa->data == pb->data)
        {
            s = (LNode *)malloc(sizeof(LNode));
            s->data = pa->data;
            rc->next = s;
            rc = s;
            pa = pa->next;
            pb = pb->next;
        }
        else if (pa->data < pb->data)
            pa = pa->next;
        else
            pb = pb->next;
    }
    return C;
}
// 习题15 求交际 并保存到A中 ab数组有序
LinkList Union(LinkList &A, LinkList &B)
{
    LNode *pa = A->next, *pb = B->next, *ra, *pre;
    A->next = NULL;
    ra = pre = A;
    while (pa && pb)
    {
        if (pa->data < pb->data)
        {
            pre = pa;
            pa = pa->next;
            //            释放掉 A中非公共元素
            free(pre);
        }
        else if (pa->data > pb->data)
            pb = pb->next;
        else
        {
            ra->next = pa;
            ra = pa;
            pa = pa->next;
        }
    }
    ra->next = NULL;
    return A;
}
// 习题16 判断B是否是A的连续字串 将来可以考虑用kmp优化一下
bool patter(LinkList A, LinkList B)
{
    // A: 122111231122
    // B:         1122
    LNode *pa = A->next, *pb, *pre; // pre 用来保存匹配失败回跳的地址
    while (pa)
    {
        //        找到相等的头元素
        if (pa->data != B->next->data)
        {
            pa = pa->next;
            continue;
        }
        pre = pa;
        pb = B->next;
        while (pa && pb)
        {
            if (pa->data != pb->data)
                break;
            else
            {
                pa = pa->next, pb = pb->next;
            }
        }
        //           B走到尽头
        if (!pb)
            return true;
        else
            pa = pre->next;
    }
    return false;
}
//习题17 判断循环双链表是否对称 这个比较简单就直接跳过 初始的过程
bool symmertry(DLinkList DL)
{
    DLNode *p = DL->next, *q = DL->prior;
    //    当长度为奇数时p、q最后会指向同一个元素 长度为奇数时候会刚好跳过去
    while (p != q || p->next != q && p->data == q->data)
        p = p->next, q = q->next;
    //    无非两种情况 链表对称 最后p和q的值一定相等 不对称的话p和q的值不行等
    return p->data == q->data ? true : false;
}

int main()
{
    LinkList L, B;
    init(L);
    init(B);
    headInsert(L, 10);
    tailInsert(L, 20);
    tailInsert(L, 40);
    insert(L, 2, 30);
    for (int i = 2; i < 5; i++)
        tailInsert(B, i * 10);
    cout << "B:  ";
    display(B);
    cout << "L:  ";
    display(L);
    //    display(L);
    //    del_tail(L);
    //    display(L);
    //    tailInsert(L,20);
    //
    //    tailInsert(L,40);
    //    delet(L,20)?cout<<"true\n":cout<<"false\n";
    //    display(L);
    //    题目要求不带头节点
    //    del_all_x(L->next,20);
    //    del_all_x_2(L,20);
    //    display(L);
    //    r_print(L->next);
    //    cout<<endl;
    //    del_min(L);
    //    display(L);
    //    reverse(L);
    //    sort(L);
    //    display(L);

    //    delByOrder(L);
    //    千万别跟display一起用 因为头节点被删了 想用的话 给delByorder的free(head)注释掉
    //    display(L);
    //    display(discreat_2(L));
    //    del_same(L);
    //    display(mergeList(L,B));
    //    display(get_common(L,B));
    //    display(Union(L,B));
    patter(L, B) ? cout << "true\n" : cout << "false\n";

    return 0;
}